package leetcode.interviewClassics;

/**
 * @author Cheng Jun
 * Description: 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像向右旋转 90 度。
 * https://leetcode-cn.com/problems/rotate-matrix-lcci/
 * 不占用额外内存空间能否做到？
 * @version 1.0
 * @date 2021/10/30 0:02
 * 面试题
 */
public class rotate {
    // 旋转图像是一道非常经典的数组题目,其中考查到嵌套循环,循环条件的边界值设置,二维坐标的转换(空间想象能力).
    // 通常,做题时会画出一个矩阵,如main方法中的matrix.但是,在多维数组中,基本上都是研究数组元素的多维下标.所以在多维数组中,应该使用带下标的矩阵.
    //
    // [a(0,0), a(0,1),...    a(0,n-2),    a(0,n-1)]
    // [a(1,0), a(1,1),...    a(1,n-2),    a(1,n-1)]
    // .
    // .
    // .
    // [a(n-2,0), a(n-2,1),...a(n-2,n-2),a(n-2,n-1)]
    // [a(n-1,0), a(n-1,1),...a(n-1,n-2),a(n-1,n-1)]
    //
    // 这样一来,矩阵就非常清晰,而且很好找出旋转过程中的下标规律.
    // 旋转90°后(上=>右), a(0,0)=>a(0,n-1), a(0,1)=>a(1,n-1), a(0,n-2) => a(n-2,n-1)
    // 观察上面的三对坐标,我们可以发现, a(i,j) => a(j, n-1-i)
    // 旋转90°后(右=>下), a(0,n-1)=>a(n-1,n-1), a(1,n-1)=>a(n-1,n-2),a(n-2,n-1)=>a(n-1,1)
    // 同样地,我们发现 a(i,j) => a(j, n-1-i).依次类推下=>左,左=>上.都是符合a(i,j) => a(j, n-1-i)规律.
    // 其实,在右=>下的过程,只是我们观察矩阵的方向和从上=>右不同而已.
    //
    // 应用 a(i,j) => a(j, n-1-i) 规律得到
    // 右边对应坐标 a(i,j) => a(j, n-1-i),
    // 下方对应坐标 a(j, n-1-i) => a(n-1-i, n-1-j),
    // 左边对应坐标 a(n-1-i, n-1-j) => a(n-1-j, i)
    //
    // 通过上面的分析,可以旋转90°,180°,270°等等.
    // 延伸扩展——将一个三维 N x N x N的矩阵表示一个正方体,将该正方体从左面推倒,左面朝上.给出推倒后的三维矩阵.
    public static void main(String[] args) {
        int[][] matrix = {
                new int[]{1, 2, 3, 4},
                new int[]{6, 7, 8, 9},
                new int[]{10, 11, 12},
                new int[]{13, 14, 15, 16},
        };
        System.out.println(matrix);
        rotate(matrix);
        System.out.println(matrix);
        for (int[] rowArr : matrix) {
            for (int col : rowArr) {
                System.out.print(col + " ");
            }
            System.out.println();
        }
    }

    // 解题思路：思考 n = 2时，从 00 位置开始，每个元素顺时针90度 转动到下一个位置，
    // 下一个位置的元素也是如此操作——顺时针90度 转动到下一个位置，直到00 位置被占用。

    // 从最外圈的数据开始考虑，处理完最外圈，再处理里面一层外圈
    static void rotate(int[][] matrix) {
        // 圈的 层次循环
        int n = matrix.length;
        for (int i = 0; i <= n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                setNext(matrix, i, j, n);
            }
        }
    }

    static void setNext(int[][] matrix, int i, int j, int n) {
        int x = matrix[j][n - i - 1];
        matrix[j][n - i - 1] = matrix[i][j];
        matrix[i][j] = matrix[n - j - 1][i];
        matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
        matrix[n - i - 1][n - j - 1] = x;
    }

    // 水平翻转后对角线对折 method2
}
